package exhaustivity.rivers;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @author longzj
 */
class RiverSolution {
    private static final int[][] PROCESS = {
            {0, -2},
            {0, -1},
            {-2, 0},
            {-1, -1},
            {-1, 0},
    };
    private static final int INIT_MAX_NUM = 3;
    private Stack<RideState> mTotalRideStates;
    private List<RideState> mResultStates;

    private RiverSolution() {
        mTotalRideStates = new Stack<>();
        mResultStates = new ArrayList<>();
    }

    public static void main(String[] args) {
        RiverSolution solution = new RiverSolution();
        solution.printResult();
    }

    void printResult() {
        final RideState rootState = new RideState(INIT_MAX_NUM, 0,
                INIT_MAX_NUM, 0, true);
        traverse(rootState);
        for (RideState state : mResultStates) {
            getSolutionStr(state, new StringBuilder());
        }
    }

    private void getSolutionStr(RideState state, StringBuilder builder) {
        String tmp = "[" + state.getLeftMonkNum() + "," + state.getLeftMonsterNum() + ","
                + state.getRightMonkNum() + "," + state.getRightMonsterNum() + "]";
        if (state.getRightMonkNum() != INIT_MAX_NUM || state.getRightMonsterNum() != INIT_MAX_NUM) {
            tmp += "->";
        }
        builder.insert(0, tmp);
        if (state.getLeftMonkNum() == INIT_MAX_NUM
                && state.getLeftMonsterNum() == INIT_MAX_NUM) {
            System.out.println(builder.toString());
            return;
        }
        getSolutionStr(state.getParentState(), builder);
    }

    private void traverse(RideState state) {
        if (isExistedInList(state)) {
            return;
        }
        if (state.getRightMonkNum() == INIT_MAX_NUM
                && state.getRightMonsterNum() == INIT_MAX_NUM) {
            mResultStates.add(state);
            return;
        }
        mTotalRideStates.push(state);
        int leftMonk, rightMonk, leftMonster, rightMonster;
        for (int[] process : PROCESS) {
            int moveMonkNum = process[0];
            int moveMonsterNum = process[1];
            boolean isLeft = state.isBoatAtLeft();
            if (!isLeft) {
                moveMonkNum = -moveMonkNum;
                moveMonsterNum = -moveMonsterNum;
            }
            leftMonk = state.getLeftMonkNum() + moveMonkNum;
            leftMonster = state.getLeftMonsterNum() + moveMonsterNum;
            rightMonk = state.getRightMonkNum() - moveMonkNum;
            rightMonster = state.getRightMonsterNum() - moveMonsterNum;
            if (checkValid(leftMonk, rightMonk, leftMonster, rightMonster)) {
                RideState childState = new RideState(leftMonk, rightMonk, leftMonster, rightMonster, !isLeft);
                childState.setParentState(state);
                traverse(childState);
            }
        }
        mTotalRideStates.pop();
    }

    private boolean checkValid(int newLeftMonk, int newRightMonk, int newLeftMonster, int newRightMonster) {
        boolean isNotNegative = newLeftMonk >= 0 && newRightMonk >= 0 && newLeftMonster >= 0 && newRightMonster >= 0;
        boolean isLeftValid = newLeftMonk == 0 || newLeftMonk >= newLeftMonster;
        boolean isRightValid = newRightMonk == 0 || newRightMonk >= newRightMonster;
        return isNotNegative && isLeftValid && isRightValid;
    }

    private boolean isExistedInList(RideState childState) {
        for (RideState state : mTotalRideStates) {
            if (state.getLeftMonkNum() == childState.getLeftMonkNum()
                    && state.getLeftMonsterNum() == childState.getLeftMonsterNum()
                    && state.isBoatAtLeft() == childState.isBoatAtLeft()) {
                return true;
            }
        }
        return false;
    }

}
